package org.example.myleet.p673;

public class Solution {
    /**
     * 动态规划，对长度和计数进行动态规划推导
     */
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] dpLen = new int[n];
        dpLen[0] = 1;
        int[] dpCount = new int[n];
        dpCount[0] = 1;
        //记录最长的长度
        int maxLen = 1;
        for (int i = 1; i < n; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (nums[i] > nums[j]) {
                    //出现递增情况
                    if (dpLen[i] < dpLen[j] + 1) {
                        //长度+1，更新长度，更新计数
                        dpLen[i] = dpLen[j] + 1;
                        dpCount[i] = dpCount[j];
                    } else if (dpLen[i] == dpLen[j] + 1) {
                        //长度相等，则进行叠加
                        dpCount[i] += dpCount[j];
                    }
                }
            }
            if (dpLen[i] == 0) {
                //非递增情况，重置长度和计数
                dpLen[i] = 1;
                dpCount[i] = 1;
            }
            maxLen = Math.max(maxLen, dpLen[i]);
        }
        //最后要通过最长的递增序列来累计数量
        int count = 0;
        for (int i = 0; i < n; ++i) {
            if (dpLen[i] == maxLen) {
                count += dpCount[i];
            }
        }
        return count;
    }
}
